package com.gxc.Interval;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class Merge {

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });

        List<int[]> list = new ArrayList<>();
        int[] prev = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            if (prev[1] >= cur[0]) {
                prev[1] = Math.max(prev[1], cur[1]);
            } else {
                list.add(new int[]{prev[0], prev[1]});
                prev = cur;
            }
        }
        list.add(new int[]{prev[0], prev[1]});


        return list.toArray(new int[list.size()][]);
    }

    /**
     * 通过模拟数组，判断连续区间，另一个思路
     * 如果这题不是连续区间，而是整数区间，那么很容易想到维护一个最大长度的Boolean数组flag（题目限制不超过10000），遍历一遍intervals并给所有出现的区间，从start到end 的 flag[i]值赋true，最后遍历flag，统计连续为true的作为一个个区间。
     * 但是提交算法发现不通过，如[[1,4],[5,6]]，正确结果是[[1,4],[5,6]]，我们的算法输出[1,6]，这是因为我们是整数区间，他会连接两个区间。
     * 解决办法就是我们让flag数组长度乘2，赋值时对应值也乘2，这样做的好处是，如上个案例，[1,4]->[2,8]，[5,6]->[10,12]，中间就会出现断点9未被赋值，从而打破了两个区间不连续的问题。
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        int n = intervals.length;
        int maxLen = 10001*2;//flag数组长度，二倍范围
        boolean[] flag = new boolean[maxLen];
        int max=-1;
        for (int i = 0; i < n; ++i) {
            max=max<intervals[i][1]*2+1?intervals[i][1]*2+1:max;
            for (int j = intervals[i][0]*2; j <= intervals[i][1]*2; ++j) {
                flag[j] = true;
            }
        }

        List<int[]> list = new ArrayList<>();
        int index = 0;
        while (index < max) {
            int[] arr = new int[2];
            while (index < maxLen && flag[index] == false) ++index;
            if (index >= maxLen) break;
            arr[0] = index/2;
            while (index < maxLen && flag[index] == true) ++index;
            arr[1] = (index - 1)/2;
            list.add(arr);
        }
        return list.toArray(new int[list.size()][]);
    }

}
